package algorithms.a06unionfind;

import com.google.common.base.Preconditions;

/**
 * 并查集 第5版
 * 压缩路径
 * 问题：压缩路径不用考虑rank？
 * 老师回答：事实上，这正是我们将这个变量叫做rank而不是叫诸如depth或者height的原因。因为这个rank只是我们做的
 * 一个标志当前节点排名的一个数字，当我们引入了路径压缩以后，维护这个深度的真实值相对困难一些，而且实践告诉我
 * 们，我们其实不需要真正维持这个值是真实的深度值，我们依然可以以这个rank值作为后续union过程的参考。因为根据
 * 我们的路径压缩的过程，rank高的节点虽然被抬了上来，但是整体上，我们的并查集从任意一个叶子节点出发向根节点前
 * 进，依然是一个rank逐渐增高的过程。也就是说，这个rank值在经过路径压缩以后，虽然不是真正的深度值，但仍然可以
 * 胜任，作为union时的参考。
 *
 * @author 王昊然
 * @create 2018-02-23 9:13
 **/
public class UnionFind5 {

    private int[] parents;
    private int count;
    private int[] ranks;//ranks[i]指以i为根，对应这棵树的层数

    public UnionFind5(int n) {
        parents = new int[n];
        count = n;
        ranks = new int[n];

        for (int i = 0; i < n; i++) {
            parents[i] = i;
            ranks[i] = 1;
        }
    }

    /**
     * 查找p对应的根，同时压缩路径
     * p即是元素下标，也是元素值，我是这么理解的
     *
     * @param p
     * @return
     */
    public int find(int p) {
        Preconditions.checkArgument(p < count, "p超出集合范围");

        /*while (p != parents[p]) {//如果一个下标的parent值是下标值，那么这是一个根节点
            //跳级，让p的父亲指向爷爷，以减少层级，当多次执行find（p）后，parents[p] == root;
            parents[p] = parents[parents[p]];
            //再让p指向爷爷的父亲，进行下一次循环
            p = parents[p];
        }
        return p;*/

        //更进一步的优化，使用递归，直到使parents[p] == root；
        //这个递归理解的不好，暂时理解为：如果p不是根，就让parents[p]指向根
        if(p != parents[p]){
            parents[p] = find(parents[p]);//注意这里参数是parents[p]不是p，递归就要让参数传递起来
        }
        return parents[p];//这里也不是p，因为递归最外层的p并未发生变化，只不过通过递归，parents[p]最终指向了根
        //思考一下：该递归结束后，p以及原来的所有父节点都已指向了root
        //讲师还是建议在实际中使用上面while循环的方式，因为对比来看递归的方式在实际中性能不一定更好，只是该方式是
        //一种思维的亮点，面试中也会是亮点
    }

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    public void unionElements(int p, int q) {

        int rootp = find(p);
        int rootq = find(q);

        if (rootp == rootq) return;

        if (ranks[rootp] < ranks[rootq]) {
            parents[rootp] = rootq;
        } else if (ranks[rootp] > ranks[rootq]) {
            parents[rootq] = rootp;
        } else{//ranks[rootp] == ranks[rootq]
            parents[rootq] = rootp;//谁指向谁无所谓
            ranks[rootp] += 1;
        }
    }

    // 测试UF1
    public static void main(String[] args){

        // 使用10000的数据规模
        int n = 70000;

        // 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间
        // 总体测试过程的算法复杂度是O(n^2)的
        //UnionFindTestHelper.testUF1(n);
        //UnionFindTestHelper.testUF2(n);
        UnionFindTestHelper.testUF3(n);
        UnionFindTestHelper.testUF4(n);
        UnionFindTestHelper.testUF5(n);
    }
}
